package GreedyAlgorithm;

import java.util.Arrays;
import java.util.HashSet;

/**
 * 两个集合，移动元素，保证两个集合的平均值最大的问题
 *
 * @author Liaorun
 */
public class MagicOp {

    public static void main(String[] args) {
        System.out.println(maxOps(new int[]{5, 6, 7, 8, 9}, new int[]{1}));
    }

    /**
     * 两个集合，移动元素，保证两个集合的平均值最大的问题
     *
     * @param arr1 数组1
     * @param arr2 数组2
     * @return 可以移动的最大次数
     */
    public static int maxOps(int[] arr1, int[] arr2) {
        double sum1 = 0;

        for (int j : arr1) {
            sum1 += j;
        }

        double sum2 = 0;

        for (int j : arr2) {
            sum1 += j;
        }

        if (sum1 / arr1.length == sum2 / arr2.length) {
            // 平均值相等，不能拿元素操作
            return 0;
        }

        // 平均值不相等
        // 指向平均值大的集合
        int[] arrMore;
        // 指向平均值小的集合
        int[] arrLess;
        // 记录平均值大的集合的和
        double sumMore;
        // 记录平均值小的集合的和
        double sumLess;

        if (sum1 / arr1.length > sum2 / arr2.length) {
            arrMore = arr1;
            sumMore = sum1;
            arrLess = arr2;
            sumLess = sum2;
        } else {
            arrMore = arr2;
            sumMore = sum2;
            arrLess = arr1;
            sumLess = sum1;
        }
        // arrMore.size < 47 use insert sort < 286 quick sort >= 286 use merge sort
        Arrays.sort(arrMore);
        // 记录小平均数的集合的元素
        HashSet<Integer> setLess = new HashSet<>();

        for (int num : arrLess) {
            setLess.add(num);
        }

        int moreSize = arrMore.length;
        int lessSize = arrLess.length;
        // 操作了多少次
        int ops = 0;

        for (int i = 0; i < arrMore.length - 1; i++) {
            // e: arrMore = [2,3,4], arrLess = [1], i = 0, moreSize = 3, lessSize = 1
            double cur = arrMore[i];
            // cur = 2
            // cur 必须大于小的平均数，小于大的平均数，且小平均数的集合中没有这个元素
            if (cur < sumMore / moreSize && cur > sumLess / lessSize && !setLess.contains(arrMore[i])) {
                // 大平均数集合拿出这个元素
                sumMore -= cur;
                moreSize--;
                // 小平均数集合放进这个元素
                sumLess += cur;
                lessSize++;
                setLess.add(arrMore[i]);
                // 一次操作成功
                ops++;
            }
        }

        return ops;
    }
}
